Search results for "Context-free grammar"

showing 8 items of 8 documents

Grammars++ for modelling information in text

1999

Abstract Grammars provide a convenient means to describe the set of valid instances in a text database. Flexibility in choosing a grammar can be exploited to provide information modelling capability by designing productions in the grammar to represent entities and relationships of interest to database applications. Additional constraints can be specified by attaching predicates to selected nonterminals in the grammar. When used for database definition, grammars can provide the functionality that users have come to expect of database schemas. Extended grammars can also be used to specify database manipulation, including query, update, view definition, and index specification.

Computer scienceViewmedia_common.quotation_subjectComputerApplications_COMPUTERSINOTHERSYSTEMScomputer.software_genreQuery languageDatabase designAdaptive grammarRule-based machine translationmedia_commonGrammarProgramming languagebusiness.industryDatabase schemaPredicate (grammar)TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESExtended Affix GrammarHardware and ArchitectureAffix grammarStochastic context-free grammarSynchronous context-free grammarArtificial intelligenceL-attributed grammarbusinesscomputerSoftwareNatural language processingInformation SystemsInformation Systems
researchProduct

Block-Deterministic Regular Languages

2001

We introduce the notions of blocked, block-marked and blockdeterministic regular expressions. We characterize block-deterministic regular expressions with deterministic Glushkov block automata. The results can be viewed as a generalization of the characterization of one-unambiguous regular expressions with deterministic Glushkov automata. In addition, when a language L has a block-deterministic expression E, we can construct a deterministic finite-state automaton for L that has size linear in the size of E.

Deterministic pushdown automatonDiscrete mathematicsDeterministic finite automatonNested wordDeterministic automatonDeterministic context-free grammarQuantum finite automataTwo-way deterministic finite automatonNondeterministic finite automatonComputer Science::Formal Languages and Automata TheoryMathematics
researchProduct

Quantum Pushdown Automata

2000

Quantum finite automata, as well as quantum pushdown automata were first introduced by C. Moore, J. P. Crutchfield [13]. In this paper we introduce the notion of quantum pushdown automata (QPA) in a non-equivalent way, including unitarity criteria, by using the definition of quantum finite automata of [11]. It is established that the unitarity criteria of QPA are not equivalent to the corresponding unitarity criteria of quantum Turing machines [4]. We show that QPA can recognize every regular language. Finally we present some simple languages recognized by QPA, two of them are not recognizable by deterministic pushdown automata and one seems to be not recognizable by probabilistic pushdown …

Discrete mathematicsNested wordComputer scienceDeterministic context-free grammarContext-free languagePushdown automatonNonlinear Sciences::Cellular Automata and Lattice GasesEmbedded pushdown automatonDeterministic pushdown automatonTuring machinesymbols.namesakeRegular languageDeterministic automatonProbabilistic automatonsymbolsQuantum finite automataAutomata theoryComputer Science::Formal Languages and Automata TheoryQuantum cellular automaton
researchProduct

Quantum Finite Multitape Automata

1999

Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [4], and by A. Kondacs and J. Watrous [3]. This notion is not a generalization of the deterministic finite automata. Moreover, in [3] it was proved that not all regular languages can be recognized by quantum finite automata. A. Ambainis and R. Freivalds [1] proved that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by deterministic or probabilistic finite automata. This …

Discrete mathematicsProbabilistic finite automataFinite-state machineNested wordComputer scienceDeterministic context-free grammarTimed automatonω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesAutomatonMobile automatonNondeterministic finite automaton with ε-movesDeterministic finite automatonDFA minimizationRegular languageDeterministic automatonProbabilistic automatonContinuous spatial automatonAutomata theoryQuantum finite automataTwo-way deterministic finite automatonNondeterministic finite automatonComputer Science::Formal Languages and Automata TheoryQuantum cellular automaton
researchProduct

Complexity of probabilistic versus deterministic automata

2005

Finite-state machineNested wordTheoretical computer scienceDFA minimizationDeterministic automatonComputer scienceDeterministic context-free grammarAutomata theoryQuantum finite automataProbabilistic analysis of algorithms
researchProduct

Why Translation Is Difficult

2017

The paper develops a definition of translation literality that is based on the syntactic and semantic similarity of the source and the target texts. We provide theoretical and empirical evidence that absolute literal translations are easy to produce. Based on a multilingual corpus of alternative translations we investigate the effects of cross-lingual syntactic and semantic distance on translation production times and find that non-literality makes from-scratch translation and post-editing difficult. We show that statistical machine translation systems encounter even more difficulties with non-literality.

Linguistics and LanguageTranslationStatistical machine translationMachine translationComputer science02 engineering and technologycomputer.software_genreMachine translation software usability050105 experimental psychologyLanguage and LinguisticsExample-based machine translationRule-based machine translation0202 electrical engineering electronic engineering information engineeringPost-editing0501 psychology and cognitive sciencesDynamic and formal equivalencebusiness.industryCommunication05 social sciencesTransfer-based machine translationLinguisticsNon-literalityComputer-assisted translation020201 artificial intelligence & image processingSynchronous context-free grammarArtificial intelligencebusinesscomputerNatural language processingHermes
researchProduct

Tally languages accepted by Monte Carlo pushdown automata

1997

Rather often difficult (and sometimes even undecidable) problems become easily decidable for tally languages, i.e. for languages in a single-letter alphabet. For instance, the class of languages recognizable by 1-way nondeterministic pushdown automata equals the class of the context-free languages, but the class of the tally languages recognizable by 1-way nondeterministic pushdown automata, contains only regular languages [LP81]. We prove that languages over one-letter alphabet accepted by randomized one-way 1-tape Monte Carlo pushdown automata are regular. However Monte Carlo pushdown automata can be much more concise than deterministic 1-way finite state automata.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESNested wordTheoretical computer scienceComputational complexity theoryComputer scienceDeterministic pushdown automatonTuring machinesymbols.namesakeRegular languageComputer Science::Logic in Computer ScienceQuantum finite automataNondeterministic finite automatonDiscrete mathematicsFinite-state machineDeterministic context-free languageComputabilityDeterministic context-free grammarContext-free languagePushdown automatonAbstract family of languagesComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Cone (formal languages)Embedded pushdown automatonUndecidable problemNondeterministic algorithmTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonsymbolsComputer Science::Programming LanguagesAlphabetComputer Science::Formal Languages and Automata Theory
researchProduct

Using Attribute Grammars for Description of Inductive Inference Search Space

1998

The problem of practically feasible inductive inference of functions or other objects that can be described by means of an attribute grammar is studied in this paper. In our approach based on attribute grammars various kinds of knowledge about the object to be found can be encoded, ranging from usual input/output examples to assumptions about unknown object's syntactic structure to some dynamic object's properties. We present theoretical results as well as describe the architecture of a practical inductive synthesis system based on theoretical findings.

business.industryComputer scienceAttribute grammarInferenceContext-free grammarInductive reasoningcomputer.software_genreObject (computer science)TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESRule-based machine translationTerminal and nonterminal symbolsFormal languageSyntactic structureArtificial intelligenceL-attributed grammarbusinesscomputerNatural language processing
researchProduct